/*
 * @lc app=leetcode.cn id=1046 lang=javascript
 *
 * [1046] 最后一块石头的重量
 */

// @lc code=start
/**
 * @param {number[]} stones
 * @return {number}
 */

var lastStoneWeight = function (stones) {
    function two_split(arr, res) {
        let left = 0
        let right = arr.length - 1
        let mid = (left + right) >> 1
        while (left < right) {
            if (arr[mid] == res) return mid
            if (arr[mid] < res) {
                left = mid + 1
            }
            if (arr[mid] > res) {
                right = mid
            }
            mid = (left + right) >> 1
        }
        return mid - 1
    }
    stones.sort((a, b) => a - b)
    while (stones.length > 1) {
        let one = stones.pop()
        let two = stones.pop()
        let res = one - two
        if (res !== 0) {
            if (res <= stones[0]) stones.unshift(res)
            else if (res >= stones[stones.length - 1]) {
                stones.push(res)
            } else {
                let index = two_split(stones, res)
                stones = stones.slice(0, index + 1).concat(res, stones.slice(index + 1))
            }
        }
    }
    return stones[0] || 0
};
// @lc code=end
lastStoneWeight([2, 7, 4, 1, 8, 1])